// 词法分析器函数，接受输入的代码字符串，并返回一个标记（token）列表
function tokenizer(input) { 
  // 当前处理的索引位置，就像一个指针在代码字符串中移动
  let current = 0; 
  // 用于存储生成的标记列表
  let tokens = []; 

  // 遍历输入的代码字符串
  while (current < input.length) { 
    // 获取当前位置的字符
    let char = input[current]; 

    // 如果字符是左括号'('
    if (char === '(') { 
      // 向标记列表中添加一个类型为'paren'（括号），值为'('的对象
      tokens.push({ type: 'paren', value: '(' }); 
      // 索引位置向后移动一位
      current++; 
      // 立即进入下一次循环，继续处理下一个字符
      continue; 
    } 

    // 如果字符是右括号')'
    if (char === ')') { 
      // 向标记列表中添加一个类型为'paren'，值为')'的对象
      tokens.push({ type: 'paren', value: ')' }); 
      current++; 
      continue; 
    } 

    // 定义一个用于匹配空白字符的正则表达式
    let whitespace = /\s/; 
    // 如果当前字符是空白字符，跳过它（索引位置向后移动一位）
    if (whitespace.test(char)) { 
      current++; 
      continue; 
    } 

    // 定义一个用于匹配数字的正则表达式
    let numbers = /\d+/; 
    // 如果当前字符是数字
    if (numbers.test(char)) { 
      let value = ''; 
      // 继续获取后面连续的数字字符，并累加到 value 中
      while (numbers.test(char)) { 
        value += char; 
        char = input[++current]; 
      } 
      // 向标记列表中添加一个类型为'number'（数字），值为累加后的数字字符串的对象
      tokens.push({ type: 'number', value }); 
      continue; 
    } 

    // 如果当前字符是双引号'"'
    if (char === '"') { 
      let value = ''; 
      char = input[++current]; 
      // 获取双引号之间的所有字符（直到遇到另一个双引号）
      while (char!== '"') { 
        value += char; 
        char = input[++current]; 
      } 
      char = input[++current]; 
      // 向标记列表中添加一个类型为'string'（字符串），值为引号内字符串的对象
      tokens.push({ type:'string', value }); 
      continue; 
    } 

    // 定义一个用于匹配字母（不区分大小写）的正则表达式
    let letters = /([a-zA-Z])/i; 
    // 如果当前字符是字母
    if (letters.test(char)) { 
      let value = ''; 
      // 继续获取后面连续的字母字符，并累加到 value 中
      while (letters.test(char)) { 
        value += char; 
        char = input[++current]; 
      } 
      // 向标记列表中添加一个类型为'name'（名称），值为累加后的字母字符串的对象
      tokens.push({ type: 'name', value }); 
      continue; 
    } 

    // 如果遇到无法识别的字符，抛出一个类型错误
    throw new TypeError(`我不认识这个字符: ${char}`); 
  } 
  // 返回生成的标记列表
  return tokens; 
} 

// 语法分析器函数，接受标记列表作为参数，并返回抽象语法树（AST）
function parser(tokens) { 
  // 初始化索引为 0
  let current = 0; 

  // 递归函数，用于遍历标记并构建抽象语法树的节点
  function walk() { 
    // 获取当前索引位置的标记
    let token = tokens[current]; 

    // 如果标记的类型是数字
    if (token.type === 'number') { 
      current++; 
      // 返回一个类型为'numberLiteral'（数字字面量）的节点，包含数字的值
      return { type: 'numberLiteral', value: token.value }; 
    } 

    // 如果标记的类型是名称（函数名）
    if (token.type ==='string') { 
      current++; 
      // 返回一个类型为'callExpression'（函数调用表达式）的节点，包含函数名和空的参数列表
      return { 
        type: 'callExpression', 
        name: token.value, 
        params: [], 
      }; 
    } 

    // 如果标记的类型是左括号'('
    if (token.type === 'paren' && token.value === '(') { 
      token = tokens[++current]; 
      // 创建一个类型为'callExpression'的节点，初始时只有函数名
      let node = { 
        type: 'callExpression', 
        name: token.value, 
        params: [], 
      }; 
      token = tokens[++current]; 
      // 当遇到的标记不是右括号')'或者是右括号但后面还有其他内容时，继续递归构建参数节点并添加到参数列表中
      while ((token.type!== 'paren' || (token.type === 'paren' && token.value!== ')'))) { 
        node.params.push(walk()); 
        token = tokens[current]; 
      } 
      current++; 
      // 返回构建好的函数调用表达式节点
      return node; 
    } 
  } 

  // 创建一个类型为'program'（程序）的根节点
  let ast = { type: 'program', body: [] }; 
  // 只要索引位置没有超出标记列表的范围，就继续递归构建节点并添加到根节点的主体中
  while (current < tokens.length) { 
    ast.body.push(walk()); 
  } 
  // 返回构建好的抽象语法树
  return ast; 
} 

// 测试示例代码
let input = '(add 2 (subtract 4 2))'; 
// 进行词法分析，得到标记列表
let tokens = tokenizer(input); 
// 对标记列表进行语法分析，得到抽象语法树
let ast = parser(tokens); 
// 打印抽象语法树
console.log(ast); 